package com.LeetCode.doublePair;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * 直方图的最大矩形
 */
public class MaxRectangle {

    public int largestRectangleArea(int[] heights) {
        int[] tmp = new int[heights.length + 2];
        System.arraycopy(heights, 0 , tmp , 1,heights.length);

        Deque<Integer> stack = new ArrayDeque<>();
        int res = 0;
        for(int i = 0; i<tmp.length; i++){
            while(!stack.isEmpty() && tmp[i] < tmp[stack.peek()]){
                int h = tmp[stack.pop()];
                res = Math.max((i - stack.peek() - 1) * h , res);
            }
            stack.push(i);
        }

        return res;

    }

    @Test
    public void test(){
        int[] arr = {2,1,5,6,2,3};
        System.out.println(largestRectangleArea(arr));
    }
}
